package main

import "fmt"

func main() {
	fmt.Printf("findAnagrams(\"cbaebabacd\", \"abc\"): %v\n", findAnagrams("cbaebabacd", "abc"))
}

/*
*
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

	异位词：子串包含p中的所有字符，每个字符的个数也相同，顺序可以不同
*/
/**
s = "cbaebabacd", p = "abc"
输出: [0,6]
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

思考：滑动窗口解决，
根据异位词的定义，可以知道滑动窗口的大小就是p的长度
所以每次循环的时候保持窗口大小不变，
左边界往右移动1个，就是丢掉一个字符，相应地，字符个数--
右边界往右移动1个，就是增加一个字符，相应地，字符个数++
利用数组可以直接比较的特性，滑动窗口内的字符的对应个数与 p字符的对应的个数相同时，下标就是了
*/
func findAnagrams(s string, p string) []int {
	if len(s) < len(p) {
		return []int{}
	}
	sCount := [26]int{}
	pCount := [26]int{}
	result := []int{}
	for index, str := range p {
		sCount[s[index]-'a']++
		pCount[str-'a']++
	}
	if sCount == pCount {
		result = append(result, 0)
	}
	for i := 0; i < len(s)-len(p); i++ {
		sCount[s[i]-'a']--
		sCount[s[i+len(p)]-'a']++
		if sCount == pCount {
			result = append(result, i+1)
		}
	}
	return result
}
